package top.minuy.subject.leetcode._695;

import java.util.*;

/**
 * 695. 岛屿的最大面积
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 * <p>
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 * <p>
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 * <p>
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 输出：6
 * 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 * 示例 2：
 * <p>
 * 输入：grid = [[0,0,0,0,0,0,0,0]]
 * 输出：0
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] 为 0 或 1
 * 通过次数140,882提交次数211,273
 *
 * @author Minuy
 * @time 13:46
 * @date 2021/11/20
 */
public class Solution {
    class Vector {
        public int x, y;

        public Vector(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vector vector = (Vector) o;
            return x == vector.x &&
                    y == vector.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    HashSet<Integer>[] g;
    HashMap<Vector, Integer> map;
    int V;
    int m, n;
    int[][] dirs4 = {
            /*{-1, -1},*/ {-1, 0}, /*{-1,  1},*/
            {0, -1}, /*{ 0,  0},*/ {0, 1},
            /*{ 1, -1},*/ {1, 0}, /*{ 1,  1},*/
    };
    boolean[] isVisited;

    public int maxAreaOfIsland(int[][] grid) {
        builderGraph(grid);

        isVisited = new boolean[V];

        int maxArea = 0;
        for (int v = 0; v < V; v++) {
            if (!isVisited[v]) {
                int count = bfs(v);
                maxArea = Math.max(maxArea, count);
            }
        }
        return maxArea;
    }

    private int bfs(int v) {
        int count = 0;
        ArrayList<Integer> queue = new ArrayList<>();
        queue.add(v);
        isVisited[v] = true;
        while (!queue.isEmpty()) {
            v = queue.remove(0);

            count++;

            for (int w : g[v]) {
                if (!isVisited[w]) {
                    queue.add(w);
                    isVisited[w] = true;
                }
            }
        }
        return count;
    }

    private void builderGraph(int[][] grid) {
        n = grid.length; // x轴
        m = grid[0].length; // y轴

        map = new HashMap<>();
        // 计算顶点总数
        V = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    // 构建坐标到序号的映射
                    map.put(new Vector(i, j), V);
                    V++;
                }
            }
        }

        // 载入顶点
        g = new HashSet[V];
        for (int i = 0;i<g.length;i++){
            g[i] = new HashSet<>();
        }
        // 计算边
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int[] ints : dirs4) {
                        int x = i + ints[0];
                        int y = j + ints[1];
                        if (x >= 0 && x < n && y >= 0 && y < m) {
                            if (grid[x][y] == 1) {
                                // 找到了一条边
                                int v1 = map.get(new Vector(i, j));
                                int v2 = map.get(new Vector(x, y));

                                g[v1].add(v2);
                                g[v2].add(v1);
                            }
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] l = {{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};

        System.out.println(new Solution().maxAreaOfIsland(l));
    }
}
